1. Technical Field
The present invention relates in general to techniques for securing the flow of information from an adversary, and in particular to techniques for verifying the identity of a communication partner and distributing session keys among communication partners.
2. Description of the Related Art
With the increased utilization of distributed data processing systems to share and communicate sensitive and confidential information, the computing and relating industries are paying significantly increased attention to improving and refining known techniques for securing data which is communicated over insecure communication channels such as telephone lines and electromagnetic-based communication systems such as cellular networks.
Three long standing industry goals exist. First, it is important that the particular communication partners in a distributed data processing system be able to authenticate the identity of other communication partners within the distributed data processing system. Commonly, this entity authentication requirement is met by depositing a long-lived and shared secret key at two or more communication nodes in the data processing system. For example, a user may possess a secret password which is also known by a host computer within the data processing system. When authentication is desired, a protocol is executed which, based on this shared secret, serves to authenticate one party to the other, or each party to the other. For example, the long-lived and shared secret key can be utilized in a conventional encryption operation such as a DES encryption. Most commonly, the communication partner desiring authentication of another partner directs a "challenge" to the other partner which is in the form of a random bit stream. The partner for which authentication is sought typically performs an encryption operation upon the challenge bit stream utilizing the long-lived and shared secret key, and then passes this data back to the challenging party. This data is decrypted to determine whether the responding party has possession or knowledge of the long-lived and shared secret key, or the challenger utilizes an encryption engine to generate the response he or she is seeking, and then compress the response to the correct answer. This operation may be performed unilaterally or bilaterally. In a unilateral operation, one party obtains authentication of the identity of another party within the distributed data processing system. In a bilateral entity authentication procedure, both parties typically issue a "challenge" to the other party, which must be responded to properly before communication can be allowed between the communication nodes.
The second broad goal of the industry is to provide techniques for generating and distributing short-lived and secret session keys which are shared by two or more communication partners in a distributed data processing system after authentication of the various communication partners has been obtained. In accordance with the present invention, the distribution of the short-lived and secret session key is tightly coupled with the entity authentication operations. The utilization of a session key ensures that the long-lived and shared secret key need not be used more often than is absolutely necessary, and it is further useful to guard against "replay attacks" across the communication sessions which communicating partners may engage in. Typically, the long-lived and shared secret key is utilized only during entity authentication operations. Immediately after authentication of the communicating parties is obtained, the short-lived and secret session key is distributed and utilized to allow communication back and forth between the parties in that particular session, to be authenticated, encrypted, or both.
The third broad industry goal is that of assuring a communicating party which has received data over an insecure line that the data has not been modified in transit. Often, such message authentication is achieved by having the originating party compute a short "authentication tag" as a function of the message being transmitted and the secret key shared by the communicating partners. This authentication tag is typically appended to the data stream which is being communicated between the parties. Upon receipt of the data stream and authentication tag, the receiving party analyzes the authentication tag by performing the same operations which were performed upon the data set by the sending party to generate its own authentication tag. If the sender's authentication tag matches identically the receiver's authenticated tag, then the recipient of the data can be assured that the data has not been altered in any way. This type of protection prevents an active adversary from entering the insecure communication channel and meddling with the data.
In devising security systems for allowing secure communication between communication partners, it is generally assumed that an adversary may be (1) passive and perform eavesdropping operations to monitor and record all communications between the parties in the distributed data processing system, or (2) active and actually participate in communications within the distributed data processing system by requesting access to data or resources and issuing or responding to authentication challenges. The capabilities of an active adversary are taken to include all those of a passive one. One type of adversarial attack which is contemplated is that of an initial passive period of monitoring and recording activities, followed by a period of off-line analysis and manipulation of the data obtained during monitoring activities, followed by a brief interval of activity wherein access to data and data processing resources is requested. Alternatively, the adversary may merely engage in passive monitoring and recording activities followed by analysis and attempts to crypt analyze portions of the data, particularly in an attempt to recover the session key, which is then utilized to decrypt any encrypted data which was transmitted between the parties and recorded by the adversary.
Since it is more difficult to detect a passive adversary, who only monitors, records, and then later performs off-line analysis, than an active adversary who is forced to interact with one or more authorized communication parties, adversaries favor a passive mode of attack. A still more significant reason off-line analysis is preferred by an adversary is the bandwidth limitations present in the communication channel: the adversary can only speak to partners at the rate which is defined and allowed by the system architecture; but off-line analysis can be performed at the rate of the adversary's computing resources. Thus, it is especially important to provide data security systems which prevent an adversary from gathering useful data during passive activities. It is especially important that security systems be designed to prevent a compromise of the long-lived and secret shared key as well as any short-lived and secret session keys which may have been utilized. It is especially important that the security system prevent the passive adversary from correctly guessing the long-lived or short-lived keys during off-line analysis, and then confirming the veracity of the guess during off-line activities. It is important that the adversary be forced to actively engage one or more communication parties in order to confirm the accuracy of a correctly guessed key. This type of protection is identified as "security against off-line attack", and can be best understood with respect to the specific example of one type of off-line attack, which is known as a "dictionary attack", which will be discussed here below.
Dictionary attacks are effective because the long-lived key used for the entity authentication is based on a user's password and these passwords are often chosen poorly. Many data processing systems allow the human operators to select their own passwords. Of course, the humans select familiar words typically, in order to be better able to remember the pass word in the future. It is not uncommon for users to use proper names or common nouns or verbs as passwords. Since human language is a fairly small and static set, it is possible for a passive adversary to iteratively guess the candidate of one or more particular languages and then see if such guess "explains" the transcript recorded in an earlier session during eavesdropping activity. When a match is identified, the correct password is typically recovered as is any short-lived key whose distribution had been based on this password. Of course, this type of off-line attack can be computationally demanding if the size of the dictionary is very large, but the significant advances which are continually being made in processing speed and power make such off-line attacks practical even if the dictionary contains many millions of words.